package com.zhang.study.chapter07;

import lombok.AllArgsConstructor;

import java.util.*;

public class Code02_TopKQuestion {

    // 暴力方法
    public List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        List<List<Integer>> ans = new ArrayList<>();
        Map<Integer, Customer> indexMap = new HashMap<>();
        // 获奖区域
        List<Customer> prizeArea = new ArrayList<>();
        // 候选区域
        List<Customer> candidateRegion = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            int userId = arr[i];
            boolean buyOrRefund = op[i];
            // 退款 而且 还没记录过此用户购买
            if (!buyOrRefund && !indexMap.containsKey(userId)) {
                // 直接记录上一次的获奖人员
                ans.add(getCurAns(prizeArea));
                continue;
            }
            // 到这里 说明 用户还剩三种情况 1. 第一次购买 2. 第j次购买 3. 退单
            // 若没有此用户 那就是第一次进来
            if (!indexMap.containsKey(userId)) {
                indexMap.put(userId, new Customer(userId, 0, 0));
            }
            Customer customer = indexMap.get(userId);
            if (buyOrRefund) {
                customer.buy++;
            } else {
                customer.buy--;
            }

            // 修改完成后，判断用户购买数量是否是0 若是0需要移除
            if (customer.buy == 0) {
                indexMap.remove(userId);
            }

            // 重新排列得奖区和候选区
            if (!prizeArea.contains(customer) && !candidateRegion.contains(customer)) {
                if (prizeArea.size() < k) {
                    customer.enterTime = i;
                    prizeArea.add(customer);
                } else {
                    customer.enterTime = i;
                    candidateRegion.add(customer);
                }
            }
            // 清除候选区和获奖区中的数量为0的用户
            clear(candidateRegion);
            clear(prizeArea);

            // 按照规则排序
            candidateRegion.sort((o1, o2) -> o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime));
            prizeArea.sort((o1, o2) -> o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime));
            // 更新得奖区和候选区
            move(prizeArea, candidateRegion, k, i);
            // 添加答案
            ans.add(getCurAns(prizeArea));
        }
        return ans;
    }


    private void move(List<Customer> prizeArea, List<Customer> candidateRegion, int k, int i) {
        if (candidateRegion.isEmpty()) {
            return;
        }
        if (prizeArea.size() < k) {
            Customer customer = candidateRegion.get(0);
            customer.enterTime = i;
            prizeArea.add(customer);
            candidateRegion.remove(0);
        } else {
            if (candidateRegion.get(0).buy > prizeArea.get(0).buy) {
                Customer prizeCustomer = prizeArea.get(0);
                prizeArea.remove(0);
                Customer candCustomer = candidateRegion.get(0);
                candidateRegion.remove(0);
                prizeCustomer.enterTime = i;
                candCustomer.enterTime = i;
                prizeArea.add(candCustomer);
                candidateRegion.add(prizeCustomer);
            }
        }
    }

    private void clear(List<Customer> list) {
        List<Customer> noZero = new ArrayList<>();
        for (Customer c : list) {
            if (c.buy != 0) {
                noZero.add(c);
            }
        }
        list.clear();
        list.addAll(noZero);
    }

    private List<Integer> getCurAns(List<Customer> prizeArea) {
        List<Integer> ans = new ArrayList<>();
        for (Customer c : prizeArea) {
            ans.add(c.id);
        }
        return ans;
    }
    
    @AllArgsConstructor
    @lombok.Data
    public static class Customer {
        public int id;

        public int enterTime;

        public int buy;
    }


    /**
     * 加强堆实现
     */
    public List<List<Integer>> topK2(int[] arr, boolean[] op, int k) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        List<List<Integer>> ans = new ArrayList<>(arr.length);
        AwardStructure structure = new AwardStructure(k);
        for (int i = 0; i < arr.length; i++) {
            int userId = arr[i];
            boolean buyOrRefund = op[i];
            structure.operate(userId, buyOrRefund, i);
            ans.add(structure.getDetailsAns());
        }
        return ans;
    }

    
    public static class AwardStructure {
        private Map<Integer, Customer> indexMap;
        private HeapGreater<Customer> prizeArea;
        private HeapGreater<Customer> candidateRegion;
        private int k;

        public AwardStructure(int limit) {
            indexMap = new HashMap<>();
            prizeArea = new HeapGreater<>((o1, o2) -> o1.buy != o2.buy ? o1.buy - o2.buy : o1.enterTime - o2.enterTime);
            candidateRegion = new HeapGreater<>((o1, o2) -> o1.buy != o2.buy ? o2.buy - o1.buy : o1.enterTime - o2.enterTime);
            k = limit;
        }

        public void operate(int userId, boolean buyOrRefund, int time) {
            if (!buyOrRefund && !indexMap.containsKey(userId)) {
                return;
            }
            if (!indexMap.containsKey(userId)) {
                indexMap.put(userId, new Customer(userId, 0, 0));
            }
            Customer customer = indexMap.get(userId);
            if (buyOrRefund) {
                customer.buy++;
            } else {
                customer.buy--;
            }
            if (customer.buy <= 0) {
                indexMap.remove(userId);
            }
            // 不在候选区也不在获奖区
            if (!prizeArea.contains(customer) && !candidateRegion.contains(customer)) {
                if (prizeArea.size() < k) {
                    customer.enterTime = time;
                    prizeArea.push(customer);
                } else {
                    customer.enterTime = time;
                    candidateRegion.push(customer);
                }
            } else if (candidateRegion.contains(customer)) { // 候选区有，候选区中数量为0，移除
                if (customer.buy == 0) {
                    candidateRegion.remove(customer);
                } else {
                    candidateRegion.resign(customer);
                }
            } else {
                // 在获奖区
                if (customer.buy == 0) {
                    prizeArea.remove(customer);
                } else {
                    prizeArea.resign(customer);
                }
            }
            move(time);
        }
        private void move(int time) {
            if (candidateRegion.isEmpty()) {
                return;
            }
            if (prizeArea.size() < k) {
                Customer customer = candidateRegion.pop();
                customer.enterTime = time;
                prizeArea.push(customer);
            } else {
                Customer candCustomer = candidateRegion.peek();
                Customer prizeCustomer = prizeArea.peek();
                if (candCustomer.buy > prizeCustomer.buy) {
                    Customer cPop = candidateRegion.pop();
                    Customer pPop = prizeArea.pop();
                    cPop.enterTime = time;
                    pPop.enterTime = time;
                    prizeArea.push(cPop);
                    candidateRegion.push(pPop);
                }
            }
        }
        public List<Integer> getDetailsAns() {
            List<Customer> customers = prizeArea.getAllElements();
            List<Integer> ans = new ArrayList<>();
            for (Customer c : customers) {
                ans.add(c.id);
            }
            return ans;
        }
    }


    // 测试
    public static class Data {
        public int[] arr;
        public boolean[] op;

        public Data(int[] a, boolean[] o) {
            arr = a;
            op = o;
        }
    }

    // 测试
    public static Data randomData(int maxValue, int maxLen) {
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        boolean[] op = new boolean[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * maxValue);
            op[i] = Math.random() < 0.5 ? true : false;
        }
        return new Data(arr, op);
    }

    public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
        if (ans1.size() != ans2.size()) {
            return false;
        }
        for (int i = 0; i < ans1.size(); i++) {
            List<Integer> cur1 = ans1.get(i);
            List<Integer> cur2 = ans2.get(i);
            if (cur1.size() != cur2.size()) {
                return false;
            }
            cur1.sort((a, b) -> a - b);
            cur2.sort((a, b) -> a - b);
            for (int j = 0; j < cur1.size(); j++) {
                if (!cur1.get(j).equals(cur2.get(j))) {
                    return false;
                }
            }
        }
        return true;
    }


    public static void main(String[] args) {

        Customer customer = new Customer(1, 1, 1);
        HashMap<Customer, Integer> hashMap = new HashMap<>();
        hashMap.put(customer, 1);
        customer.buy--;
        Integer integer = hashMap.get(customer);
        System.out.println(integer);
        int maxValue = 10;
        int maxLen = 5;
        int maxK = 6;
        int testTimes = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            ;
            Data testData = randomData(maxValue, maxLen);
            int k = (int) (Math.random() * maxK) + 1;
            int[] arr = testData.arr;
            boolean[] op = testData.op;
            List<List<Integer>> ans1 = new Code02_TopKQuestion().topK(arr, op, k);
            List<List<Integer>> ans2 = new Code02_TopKQuestion().topK2(arr, op, k);
            if (!sameAnswer(ans1, ans2)) {
                for (int j = 0; j < arr.length; j++) {
                    System.out.println(arr[j] + " , " + op[j]);
                }
                System.out.println(k);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("出错了！");
                List<List<Integer>> ans3 = new Code02_TopKQuestion().topK2(arr, op, k);

                break;
            }
        }
        System.out.println("测试结束");
    }


    public static class HeapGreater<T> {
        private List<T> heap;
        private int heapSize;
        private Comparator<T> comp; // 默认比较器
        /**
         * 反向索引表
         */
        private HashMap<T, Integer> indexMap;


        public HeapGreater(Comparator<T> comp) {
            this.comp = comp;
            heap = new ArrayList<>();
            heapSize = 0;
            indexMap = new HashMap<>();
        }

        public boolean isEmpty() {
            return heapSize == 0;
        }

        public int size() {
            return heapSize;
        }

        public boolean contains(T obj) {
            return indexMap.containsKey(obj);
        }

        public T peek() {
            return heap.get(0);
        }

        public void push(T obj) {
            heap.add(obj);
            indexMap.put(obj, heapSize);
            heapInsert(heapSize++);
        }

        public T pop() {
            T ans = heap.get(0);
            swap(0, heapSize - 1);
            indexMap.remove(ans);
            heap.remove(--heapSize);
            heapify(0);
            return ans;
        }

        public void remove(T obj) {
            // 找到最后一个元素 用于替换移除的元素
            T replace = heap.get(heapSize - 1);
            // 找到需要移除的元素的下标
            Integer index = indexMap.get(obj);
            // 反向索引表中直接移除
            indexMap.remove(obj);
            // 堆中直接移除最后一个 然后一会用移除元素来替换最后这个元素
            heap.remove(--heapSize);
            // 判断下需要移除的元素是不是最后一个 如果不是 再替换
            if (replace != obj) {
                heap.set(index, replace);
                indexMap.put(replace, index);
                resign(replace);
            }

        }

        public void resign(T obj) {
            Integer index = indexMap.get(obj);
            heapInsert(index);
            heapify(index);
        }

        private void heapify(int i) {
            int left = 2 * i + 1;
            while (left < heapSize) {
                int largest = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
                largest = comp.compare(heap.get(largest), heap.get(i)) < 0 ? largest : i;
                if (largest == i) {
                    break;
                }
                swap(i, largest);
                i = largest;
                left = 2 * i + 1;
            }
        }


        private void heapInsert(int index) {
            while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void swap(int i, int j) {
            T o1 = heap.get(i);
            T o2 = heap.get(j);
            heap.set(i, o2);
            heap.set(j, o1);
            indexMap.put(o1, j);
            indexMap.put(o2, i);
        }


        public List<T> getAllElements() {
            return new ArrayList<>(heap);
        }

    }

}
